/**
 * @Question.Title: 和至少为 K 的最短子数组
 * @Question.No: 862
 * @Author: DQ
 * @Date: 2021-04-15 15:55:11
 * @Description: 
 */
//返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。 
//
// 如果没有和至少为 K 的非空子数组，返回 -1 。 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 输入：A = [1], K = 1
//输出：1
// 
//
// 示例 2： 
//
// 输入：A = [1,2], K = 4
//输出：-1
// 
//
// 示例 3： 
//
// 输入：A = [2,-1,2], K = 3
//输出：3
// 
//
// 
//
// 提示： 
//
// 
// 1 <= A.length <= 50000 
// -10 ^ 5 <= A[i] <= 10 ^ 5 
// 1 <= K <= 10 ^ 9 
// 
// Related Topics 队列 二分查找 
// 👍 274 👎 0

package dq.leetcode.editor.cn;

public class ShortestSubarrayWithSumAtLeastK {
    public static void main(String[] args) {
        Solution solution = new ShortestSubarrayWithSumAtLeastK().new Solution();
        int[] A = new int[]{1};
        int K = 1;
        System.out.println(solution.shortestSubarray(A, K));
    }
        //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int shortestSubarray(int[] A, int K) {
        // {1,2,3,4}
        //{0,1,3,6,10}
        int[] prex = new int[A.length+1];
        for(int i = 1; i < prex.length; i++){
            prex[i] = A[i-1] + prex[i-1];
        }
        int ans = Integer.MAX_VALUE;
        for(int i = prex.length-1; i > 0; i--){
            for (int j = i-1; j >= 0 && j-i < ans; j--){
                if(prex[i] - prex[j] >= K ) {
                    ans = Math.min(i - j, ans);
                    break;
                }
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}